/**************************************************************************
* File:            graph.h	                                              *
* Description:     Two implementations of graph - incidence list/matrix   *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/

#pragma once

#include <vector>
#include <functional>
#include <memory>
#include <iostream>

struct Edge{
	int from, to;
	Edge(){}
	Edge(int from, int to) :from(from), to(to){}
	bool operator ==(const Edge &x)const{
		return x.from == from && x.to == to;
	}
	bool operator !=(const Edge &x)const{
		return !(*this == x);
	}
	bool operator <(const Edge &x)const{
		return from < x.from || (from == x.from && to < x.to);
	}
};


class Graph{
public:
	virtual int getVerticesNumber() const = 0;
	virtual std::vector<int> getIncidenceList(int vertex) const = 0;
	virtual ~Graph(){}
};

class ListBasedGraph :public Graph{
	int verticesNumber_;
	int edgesNumber_;
	std::vector<std::vector<int> > incidenceList_;
public:
	ListBasedGraph(const std::vector<Edge> &edges,const int verticesNumber_):
		verticesNumber_(verticesNumber_), incidenceList_(verticesNumber_), edgesNumber_(edges.size()){

		for (auto &edge : edges){
			incidenceList_[edge.from].push_back(edge.to);
		}

	}

	std::vector<int> getIncidenceList(int vertex)const{
		return incidenceList_[vertex];
	}

	int getVerticesNumber()const{
		return verticesNumber_;
	}

};

class MatrixGraph :public Graph{
	int verticesNumber_;
	std::vector<std::vector<bool> >  incidenceMatrix_;
public:
	MatrixGraph(const std::vector<Edge> &edges, const int verticesNumber_) :verticesNumber_(verticesNumber_){
		incidenceMatrix_.resize(verticesNumber_);

		for (auto &row : incidenceMatrix_){
			row.resize(verticesNumber_);
		}

		for (auto &edge : edges){
			incidenceMatrix_[edge.from][edge.to] = true;
		}
	}

	int getVerticesNumber()const{
		return verticesNumber_;
	}

	std::vector<int> getIncidenceList(int vertex)const{
		std::vector<int> adjacent;

		for (int i = 0; i < verticesNumber_; ++i)
		if (incidenceMatrix_[vertex][i]){
			adjacent.push_back(i);
		}

		return adjacent;
	}
};

std::unique_ptr<Graph> makeCompactGraph(std::vector<Edge> edges, int verticesNumber){
	size_t matrixSize = verticesNumber * verticesNumber;
	size_t listSize = 2 * edges.size() * sizeof(int);

	if (matrixSize < listSize)
		return std::unique_ptr<Graph> (new MatrixGraph(edges, verticesNumber));
	else
		return std::unique_ptr<Graph> (new ListBasedGraph(edges, verticesNumber));
}



